1. Field of the Invention
This invention relates to the generation of half tone patterns for printing and graphical displays and, more particularly, to providing a user interface for describing how the spots forming such half tone patterns are to be formed as a function of the overall density of an area to be printed or displayed.
2. Summary of the Background Art
Halftone patterns are used to convert continuous tone gray and color images into binary patterns to produce many different kinds of printed images or graphics. This conversion step is necessary because most printing processes are binary in nature, locally producing only an area having no ink or an area completely covered by a layer of ink. Such printing processes include mass production processes, such as letterpress printing and offset printing, as well as computer output printing.
The idea of producing images from black, white, and colored spots is not new, being well represented in the form of mosaic tile images formed in the first century BC in Pompeii. In the last two decades of the nineteenth century, a group of artists known as the pointillists produced paintings formed by arrays of colored dots, which were seen as realistic scenes when viewed from sufficient distances. These artists, notably Georges Seurat and Paul Signac, studied color theory to determine how one color affects other colors around it, as seen by the human eye, and applied paint to canvas in units, or little dots. Their work influenced the development of modern color printing processes, which use four colors—cyan, yellow, magenta, and black—along with the white background of paper before printing, to represent full color images. Because of the binary nature of most printing processes used for the printing of each of these colors, a separate halftone pattern is usually used to form an image in each color.
Printers operating with computer systems to produce individual copies of documents are typically either electrophotographic devices or ink jet devices. The electrophotographic devices tone electrostatic images on a photoconductive surface after the images have been formed by electrically charging the surface and by discharging areas to form the image, typically with light from a laser driven by a signal derived from the image to be printed. Toner from the photoconductive surface is then transferred to the surface of the paper and fused on the paper with heat. While electrophotographic printing has some ability to print continuous tones, much better results are typically obtained when halftone images are printed.
A computer output printer generally prints dots on paper corresponding to information stored in a pixel map within the computer system, with data being transmitted from the computer system to the printer according to a PDL (page description language), such as POSTSCRIPT (a registered trademark of Adobe Systems, Inc.), which is independent of the type of printer, or, alternately according to a PCL (Printer Control Language), such as a version of a language developed by Hewlett Packard, that is dependent on the type of printer. For example, an image is represented and stored in a page description format as a PDL file including one or more objects to be printed. The printer then interprets the objects within the PDL file, rendering the data as a pixel map stored within a frame buffer.
For halftone printing of a grayscale image using an electrophotographic printer, locations corresponding to the area in which an image can be printed are divided into a number of halftone cells, each of which includes a number of device pixels that can be individually printed as dark areas or left white by the printer. For each device pixel, the intensity of a corresponding area of the original image is compared with a threshold level, with the printer then being conditioned to print the pixel area dark if the threshold value exceeds a number representing the intensity of the corresponding area of the original image and otherwise to leave the pixel area white. The number representing the intensity of the corresponding area of the original image is derived from the gray level of the original image, being, for example, a number between zero and 255 in an 8-bit system where white is 255. For each device pixel, the threshold value is derived from a threshold array of values representing the spot pattern of the halftone.
For halftone printing of a color image using an electrophotographic printer, the process described above for a grayscale image is repeated for each of several tonal images formed when the color image is separated into several colors. Typically, separate images of cyan, yellow, magenta, and black are used in a four-color printing process. The halftone patterns formed for these colors are typically rotated with respect to one another.
The halftone patterns used in electrophotographic printing are typically formed on a constant line frequency grid having a fixed spacing between adjacent individual dots in both horizontal and vertical directions. The size of an individual dot, and its shape, depend on the local optical density, when viewed from a suitable distance, of the gray or color image to be printed. On the other hand, ink jet devices typically produce stochastic, or frequency modulated halftone patterns, with small drops of ink. The halftone patterns used in electrophotographic printing are typically composed of spots that vary in shape as well as size with changes in density. Since characteristics of the printing process affect the ways in which a halftone pattern is actually printed, it is desirable to consider these characteristics in developing the specifications of halftone patterns for a particular type of printer. While spots below a certain size do not print reliably spots large enough to print exhibit a phenomenon known as dot gain, which enlarges the spots to some degree, especially effecting relatively small spot sizes. As spots increase in size, corresponding to images of increasing overall darkness, they begin to touch, with toner being deposited additionally in the narrowing areas adjacent the lines along which the spots touch. This results in a phenomenon known as tonal jump, with the density of the printed pattern rapidly changing in response to a gradual change in the density of the image being reproduced. As the spots increase in size to nearly fill the paper, the small gaps among adjacent spots reach a point in which they are filled with toner, as a result of a phenomenon known as plugging.
FIG. 1 is an enlarged view of a Euclidean halftone pattern, showing spot shapes formed to achieve densities, in terms of an intensity defined as the ratio of the white paper area remaining after printing to total area, varying from 0 at a left end to 1.0 at a right end. As this intensity is decreased from 1.0 to 0.5, the spots are changed from small round dots 2 to larger round dots 4, to diamonds 5. As the intensity is further decreased from 0.5 to 0, the pattern is formed by spaces between adjacent spots, with these spaces being formed as increasingly small round areas. This pattern provided good results, since the small areas, whether black or white, are all round, minimizing the dot gain of the black areas and the problems of plugging the white areas. A tonal jump occurs as the adjacent diamond-shaped spots touch at an intensity of 0.5. The advantages of this type of pattern make it the most widely used halftone pattern today.
U.S. Pat. No. 6,198,545 describes a method for generating halftone patterns including screen elements with sophisticated spot shapes such as artistic shapes, microletters, and ideograms. The method can be used to generate screen elements having spots made of artistic shapes evolving with increasing levels of density. For generating screen elements at consecutive intensity levels, intermediate contours that bound the black and white parts of each screen element are obtained by interpolating between fixed predefined contours. The process can be used to generate discrete subscreen elements having geometries varying from one subscreen spot to another for the same density level. Some subscreen dot variations may be used to avoid counterfeiting by photocopying machine and digital scanners, making the process useful for printing banknotes, postage stamps, or valuable papers. The two fixed predefined contours are provided as inputs during the process of designing the halftone pattern, being described, for example, as a sequence of curve segments represented by spline functions, such as functions of third order Bezier curves, in a method commonly used by interactive curve drawing software packages.
While a line segment may be provided as an input to a computer system by providing the values of parameters within an equation defining the line segments in two- or three-dimensional space, together with limits establishing each end of the segment, this method is cumbersome and not intuitive for use in the design process. Therefore, a number of graphical methods have been developed for providing user inputs describing and modifying such line segments. One of these methods involves the treatment of the line segment as a spline having a number of control vertices, each of which is a point in two- or three-dimensional space. Taken together, the control vertices define the beginning and end of the line segment and its shape by defining the parameters of the mathematical equation of the line segment. A straight line segment is defined by only two control vertices, which are placed at its ends. In general, a control vertex establishes each end of a curved line segment, with one of more additional control vertices, displaced away from the line segment, establishing the shape of the line segment between its ends according to previously established mathematical relationships.
Thus, data defining a line segment as a spline is provided by a user establishing the locations of the various control vertices by typing their coordinates or by selecting their position using a pointing device, such as a mouse. The shape of the line segment may then be further modified by moving the control vertices, or by adding or deleting control vertices. This method is used, for example, in computer assisted drafting with AUTOCAD@, and in the generation of animation objects for film production in MAYA®. The processing of data to evaluate spline functions is further discussed in European Patent Application 0425177 A2, The mathematical interpolation associated with the generation of parameters for splines may further be used in a convergence adjusting apparatus for a projection image display device, as described in U.S. Pat. No. 6,373,535.
Another method for creating a surface of a three-dimensional model is described in U.S. Pat. No. 5,739,822, with the method being performed in a system characterized by identification means for identifying data representing a plurality of lines forming a first closed loop consisting of edges meeting at nodes, and for retrieving such data from a storage device, and processing means for generating data defining a series of additional loops to represent a candidate surface bound by the first closed loop. Additionally, the processing means is adapted to receive data representing a line defined by the user via the input means, which subdivides the first closed loop into a plurality of new closed loops, and then to edit the candidate surface by generating a further series of closed loops for each new closed loop.
A method for automatically calibrating the operation of an output device, such as a printer, based on the output mode of the device, is described in U.S. Pat. No. 6,067,406, with the output mode being characterized by user-selectable settings, such as paper type and ink type. Apart from screen characteristics, such as screen ruling, frequency, and angle, a calibration curve are communicated via the page description language, such as POSTSCRIPT® Level 2, for each color component. Sets of calibration curves are prepared for specific types of rendering, being referenced by name. Through this name identification and through naming conventions based upon the output mode or screening parameters, calibration changes are introduced quickly and consistently.
What is needed is a method for generating a halftone spot function quickly, from an input describing its cross-sectional shape along one or two axes. Additionally, what is needed is an efficient method for generating a halftone pattern using tileable supercells, each including a number of halftone cells that are not themselves tileable horizontally and vertically because of the angles at which they are skewed and inclined.